/*
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */
package item10;

import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

/**
 * <p>
 *
 * </p>
 * @author LvJing
 * @version $Id:Fibonacci.java v1.0 2018/7/14 下午5:55 LvJing Exp $
 */
public class Fibonacci {

    private Solution solution;

    @Before
    public void init() {
        solution = new Solution();
    }

    /**
     * 特殊输入测试  -5
     */
    @Test
    public void test01() {
        Assert.assertEquals(-1, solution.Fibonacci(-5));
    }

    /**
     * 功能测试0，1，2，3，4，5项
     */
    @Test
    public void test02() {
        Assert.assertEquals(0, solution.Fibonacci(0));
        Assert.assertEquals(1, solution.Fibonacci(1));
        Assert.assertEquals(1, solution.Fibonacci(2));
        Assert.assertEquals(2, solution.Fibonacci(3));
        Assert.assertEquals(3, solution.Fibonacci(4));
        Assert.assertEquals(5, solution.Fibonacci(5));
    }
}

/**
 * 面试题10：斐波那契数列，求第n项
 * 斐波那契数列定义：  f(n) = 0(n==0); = 1(n==1);  =  f(n-1)+f(n-2) (n>1)
 *
 * 思路：这个题是很多教材上都讲过的，但是都是用来引入递归思想拿来举例子的，但其实它并不太适合用递归来做，因为存在很大的性能问题，首先是递归本身
 * 就会存在调用栈溢出问题，同时对于这个数列，存在很大的重复计算问题，比如求第10项，那么需要先求9和8，而9又需要求8和7，这样的性能是很低的。
 * 这里用循环来实现，其实只要是能用递归实现的算法，就能用循环来实现，只不过循环实现的代码量要多一些。循环的思路为，通过自下而上，先求小的，再求大的，
 *
 */
class Solution {

    int Fibonacci(int n) {
        if (n < 0) {
            return -1;
        }

        int[] init = { 0, 1 };
        if (n < 2) {
            return init[n];
        }

        // f(n-1)
        int stepOne = 1;
        // f(n-2)
        int stepTwo = 0;
        // f(n)
        int result = 0;
        for (int i = 2; i <= n; i++) {
            result = stepOne + stepTwo;
            stepTwo = stepOne;
            stepOne = result;
        }
        return result;
    }
}
